package leetcode.hash和set;

import java.util.*;

/**
 * 两个数组的交集
 * <p>
 * 给定两个数组，编写一个函数来计算它们的交集。
 * <p>
 * 总体时间复杂度：O(n)
 * <p>
 * 空间复杂度：S(n)
 */
public class Test349两个数组的交集 {

    public static int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> res = new HashSet<>();
        // O(n) ==> 遍历数组是 n，往 set 里面插入数据是 1
        for (int n : nums1)
            set.add(n);
        // O(n)
        for (int n : nums2)
            if (set.contains(n))
                res.add(n);
        int[] result = new int[res.size()];
        int index = 0;
        // O(n)
        for (int n : res)
            result[index++] = n;
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 2, 1, 3};
        int[] nums2 = new int[]{2, 2, 1};
        int[] ans = intersection(nums1, nums2);
        Integer[] ans2 = intersection2(nums1, nums2);
        System.out.println(Arrays.toString(ans));
        System.out.println(Arrays.toString(ans2));
    }

    /**
     * 求交集，就是找出 nums1 和 nums2 里面一样的数据
     *
     * @param nums1
     * @param nums2
     */
    public static Integer[] intersection2(int[] nums1, int[] nums2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        // 去重
        Arrays.stream(nums1).distinct().forEach(list1::add);
        Arrays.stream(nums2).distinct().forEach(list2::add);

        // 求交集
        list1.retainAll(list2);

        // 求差集
//        list1.removeAll(list2);


        // 求并集
//        list1.removeAll(list2);
//        list1.addAll(list2);

        Integer[] ans = list1.stream().toArray(Integer[]::new);
        return ans;
    }
}
